#include "BinarySortTree.h"
#include "CircleQueue.h"
#include <stdio.h>
#include <stdlib.h>
/*
	Insert_node:往r指向的二叉排序树中加一个数据为d的结点
		返回二叉排序树的根结点的地址
*/
BTnode *Insert_node(BTnode *r,TreeData d)
{
	/*step1: 先创建一个结点*/
	BTnode *pnew = (BTnode *)malloc(sizeof(*pnew));
	pnew->data = d;
	pnew->lchild = NULL;
	pnew->rchild = NULL;
	/*step2:把结点加入到二叉排序树中*/
	if(r == NULL)//此时为空树
	{
		return pnew;//此时pnew将作为根结点返回
	}
	BTnode *p = r;//遍历指针
	while(1)
	{
		if(pnew->data < p->data)
		{
			if(p->lchild == NULL)//如果p没有左孩子，直接挂载
			{
				p->lchild = pnew;
				break;
			}
			p = p->lchild;
		}
		else if(pnew->data > p->data)
		{
			if(p->rchild == NULL)
			{
				p->rchild = pnew;
				break;
			}
			p = p->rchild;
		}
		else//相等
		{
			printf("数据重复!!\n");
			break;
		}
	}

	return r;
}

/*
	根据用户的输入创建一个二叉排序树并返回根结点的地址
*/
BTnode *create_sort_tree()
{
	BTnode *r = NULL;//用来保存根结点的地址
	TreeData d;
	while(1)
	{
		scanf("%d",&d);
		if(d == 0)
		{
			break;
		}
		r = Insert_node(r,d);
	}

	return r;
}
/*
	delete_node：在r指向的二叉排序树中删除值为x的结点 
		删除完之后仍然为二叉排序树
		返回根结点的地址
*/
BTnode *delete_node(BTnode *r,TreeData x)
{
	/*step1:找到值为x的结点*/
	BTnode *p = r;//p指向要删除的结点 
	BTnode *pre = NULL;//pre指向p的父结点 
	while(p)
	{
		if(p->data == x)
		{
			break;
		}
		else if(p->data < x)
		{
			pre = p;
			p = p->rchild;
		}
		else
		{
			pre = p;
			p = p->lchild;
		}
	}
	//没找到
	if(p == NULL)
	{
		return r;
	}
	/*step2:删除p指向的结点*/
	if(p->lchild == NULL && p->rchild == NULL)//p没有孩子
	{
		//特殊情况 p是根结点
		if(p == r)
		{
			free(p);
			return NULL;
		}
		//两种情况 
		if(p == pre->lchild)
		{
			pre->lchild = NULL;
			free(p);
		}
		else if(p == pre->rchild)
		{
			pre->rchild = NULL;
			free(p);
		}
	}
	else if(p->lchild != NULL && p->rchild != NULL)//p有两个孩子
	{
		BTnode *p2 = p->lchild;//p2指向p的左子树中最大的结点
		BTnode *pre2 = p;//pre2指向p2的父结点 
		if(p2->rchild == NULL)//p的左孩子就是最大的结点
		{
			p->data = p2->data;
			p->lchild = p2->lchild;
			p2->lchild=NULL;
			free(p2);
		}
		else
		{
			while(p2->rchild)
			{
				pre2 = p2;
				p2 = p2->rchild;
			}
			p->data = p2->data;
			pre2->rchild = p2->lchild;
			p2->lchild = NULL;
			free(p2);
		}
	}
	else//p只有一个孩子
	{
		if(p == r)//p为根结点
		{
			if(p->lchild)
			{
				BTnode *ret = p->lchild;
				p->lchild = NULL;
				free(p);
				return ret;
			}
			else
			{
				BTnode *ret = p->rchild;
				p->rchild = NULL;
				free(p);
				return ret;
			}
		}
		if(p == pre->lchild)//p为pre的左孩子
		{
			if(p->lchild)
			{
				pre->lchild = p->lchild;
				p->lchild = NULL;
				free(p);
			}
			else
			{
				pre->lchild = p->rchild;
				p->rchild = NULL;
				free(p);
			}
		}
		else//p是pre的右
		{
			if(p->lchild)
			{
				pre->rchild = p->lchild;
				p->lchild = NULL;
				free(p);
			}
			else
			{
				pre->rchild = p->rchild;
				p->rchild = NULL;
				free(p);
			}
		}
	}

	return r;
}
/*
	递归删除二叉树中任意的结点
*/
BTnode *delete_node_r(BTnode *r,TreeData x)
{
	if(r == NULL)
	{
		return NULL;
	}
	if(x < r->data)
	{
		r->lchild = delete_node_r(r->lchild,x);//在r的左子树中去找到x并且删掉
	}
	else if(x > r->data)
	{
		r->rchild = delete_node_r(r->rchild,x);//在r的右子树中去找到x并且删掉
	}
	else//r就是你要删除的结点
	{
		if(r->lchild != NULL)//r有左子树，则找左子树中最大的结点，交换值
		{
			BTnode *p = r->lchild;
			while(p->rchild != NULL)
			{
				p = p->rchild;
			}
			r->data = p->data;//
			r->lchild = delete_node_r(r->lchild,p->data);//在r的左子树中删除p的值
		}
		else if(r->rchild != NULL)//r在没有左子树的情况下，找右子树中最小的结点，交换值
		{
			BTnode *p = r->rchild;
			while(p->lchild != NULL)
			{
				p = p->lchild;
			}
			r->data = p->data;//
			r->rchild = delete_node_r(r->rchild,p->data);//在r的右子树中删除p的值
		}
		else//直到r为叶子结点就删除
		{
			free(r);
			return NULL;
		}
	}

	return r;
}

/*---------------先序、中序、后序----------------------*/
/*先序:根 左 右*/
void pre_order(BTnode *r)
{
	if(r == NULL)
	{
		return ;
	}
	/*step1：输出根结点*/
	printf("%d ",r->data);
	/*step2: 用先序的方式往左子树遍历*/
	pre_order(r->lchild);
	/*step3: 用先序的方式往右子树遍历*/
	pre_order(r->rchild);
	
}
/*中序:左 根 右*/
void mid_order(BTnode *r)
{
	if(r == NULL)
	{
		return ;
	}
	/*step1: 用中序的方式往左子树遍历*/
	mid_order(r->lchild);
	/*step2：输出根结点*/
	printf("%d ",r->data);
	/*step3: 用中序的方式往右子树遍历*/
	mid_order(r->rchild);
}
/*后序:左 右 根*/
void post_order(BTnode *r)
{
	if(r == NULL)
	{
		return ;
	}	
	/*step1: 用后序的方式往左子树遍历*/
	post_order(r->lchild);
	/*step2: 用后序的方式往右子树遍历*/
	post_order(r->rchild);
	/*step3：输出根结点*/
	printf("%d ",r->data);
}
/*层次遍历：使用队列完成层次遍历输出 */ 

void level_print(BTnode *r)
{
	if(r == NULL)
	{
		return ;
	}
	/*step1：先创建一个队列*/
	struct CqQueue *c =InitQueue();
	EnQueue(c,r);//把根结点入队 
	/*step2：循环判断队列是否为空 不为空就出队元素*/
	while(!QueueIsEmpty(c))
	{
		/*step3:先出队元素并打印数据域*/
		Datatype p = DeQueue(c);
		printf("%d ",p->data);
		//先判断出队元素是否有左孩子，如果有就把左孩子入队
		if(p->lchild)
		{
			EnQueue(c,p->lchild);
		}
		//再判断出队元素是否有右孩子，如果有就把右孩子入队
		if(p->rchild)
		{
			EnQueue(c,p->rchild);
		}
	}
	printf("\n");

	DestroyQueue(c);
}

